package com.algorithm.example;

/**
 * <p>
 * 复杂度
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/15 11:57
 */
public class Complexity {

    // -----------事前预计法------------------
    // --------------时间复杂度---------------

    /**
     * 线性查找法
     */
    public static int linearity(int[] A, int target) {
        for (int i = 0; i < A.length; i++) {
            if (A[i] == target) {
                return i;
            }
        }
        return -1;
    }
    /*
        按照最坏的情况来查找（没找到）
       int i = 0;                1
       i < A.length;             n+1
       i++;                      n
       if(A[i] == target)        n
       return -1;                1

       3 * n + 1

       当数组为1024个元素时，时间复杂度为:  3*1024+1 = 3073
     */


    /**
     * 改动版二分查找
     */
    public static int dichotomyPlus(int[] A, int target) {
        int i = 0;
        int j = A.length; // 定义为不参与计算的边界值
        while (i < j) { // j不参与计算
            int m = (i + j) >>> 1;
            if (A[m] < target) { // 在右边
                i = m + 1; //
            } else if (target < A[m]) { // 在左边
                j = m;
            } else {
                return m;
            }
        }
        return -1;
    }

    /*
        按照最坏的情况来查找（最右边没找到）
        int i = 0; int j = A.length;              2
        return -1;                                1
        i < j                                     floor(log_z(n) + 1
        int m = (i + j) >>> 1                     floor(log_z(n) + 1
        A[m] < target                             floor(log_z(n) + 1
        target < A[m]                             floor(log_z(n) + 1
        j = m                                     floor(log_z(n) + 1

        总次数: 5 * ( floor(log_z(n) + 1) + 3
        当数组为1024个元素时，时间复杂度为:  5 * ( floor(log_z(1024) + 1) + 3 = 58

     */

    /*

        元素个数          循环个数
        4-7               3
        8-15              4
        16-31             5
        32-63             6
        ...               ...
        2^n-2^n+1         n+1  -> floor(log_z(n) + 1
     */

    /**
     * 改动版二分查找
     */
    public static int dichotomyPlus2(int[] A, int target) {
        int i = 0;
        int j = A.length; // 定义为不参与计算的边界值
        while (i < j) { // j不参与计算
            int m = (i + j) >>> 1;
            if (A[m] < target) { // 在右边
                i = m + 1; //
            } else if (target < A[m]) { // 在左边
                j = m;
            } else {
                return m;
            }
        }
        return -1;
    }

    /*
        空间复杂度
        int i = 0;                    4个字节
        int j = A.length - 1 ;        4个字节
        int j = m - ;                 4个字节

     */


}
